package com.heima.algorithm.recursion;

/**
 * <h2>插入排序</h2>
 * <ul>
 *     <li>将数组分为两部分：[0……low-1]和[low……arr.length - 1]</li>
 *     <li>[0……low-1]有序部分，也就是待插入部分</li>
 *     <li>[low……arr.length - 1]无序部分</li>
 *     <li>把arr[low]的值记下来，在有序部分中找到比low小或等的第一个元素，后面的右移，再插入arr[low]，找不到比它小的，也就是无序部分全部右移，则插入索引零的位置</li>
 * </ul>
 */
public class InsertionSort {

    /**
     * 对外界提供的插入排序
     * @param arr 待排序的数组
     */
    public static void insertionSort(int[] arr) {
        insertionSort(arr,1,arr.length - 1, 0); // 如果是0会发现第一次递归啥也没做，可以说自定义第一个元素是排好序的，因为一个元素排序未排序没区别
    }

    /**
     * 指定区间内进行插入排序
     * @param arr 待排序的数组
     * @param startIndex 开始索引 （包含）
     * @param endIndex 结束索引（包含）
     */
    public static void insertionSort(int[] arr,int startIndex, int endIndex){
        insertionSort(arr,startIndex + 1, endIndex, startIndex);
    }

    /**
     * 递归插入排序，一次递归是将无序部分的第一个元素插入到有序部分
     * @param arr 待排序的数组
     * @param low 无序部分的左边界（包含）
     * @param endIndex 无序部分的上边界,也是指定范围进行排序的上界（包含）
     * @param startIndex 指定范围进行排序的下届
     */
    private static void insertionSort(int[] arr, int low, int endIndex, int startIndex) {
        if (low == endIndex + 1){
            return;
        }
        int inserted = arr[low];
        int i = low - 1;
        while (i >= startIndex && arr[i] > inserted) {
            arr[i + 1] = arr[i];
            i--;
        }
        if (arr[i + 1] == low) {
            arr[i + 1] = inserted;
        }
        insertionSort(arr,low + 1, endIndex, startIndex);
    }
}
